The present invention relates to analyzing multi-threaded programs. More specifically, the invention relates to modifying the predisposed execution of a multi-threaded program to detect and cause latent deadlocks.
Traditional computer programs involved a single execution stream that performed operations sequentially. However, it is now common for computer programs to include multiple execution streams, which can perform operations in parallel. Each instruction stream is known as a “thread.”
Multi-threaded programs allow for better utilization of the computer system's resources. For example, where a traditional single-threaded program awaits for user input and wastes processing power, a multi-thread program can have a thread perform operations in the “background” while a different thread is processing the user input. Thus, a multi-threaded word processing program can perform spell checking or a multi-threaded spreadsheet program can recalculate the spreadsheet in the background to achieve more efficient utilization of processing power.
Although multi-threaded programs can provide better utilization of the computer system's resources, the dynamic execution of threads makes debugging the programs very difficult. Errors in thread synchronization may be rarely manifested during program execution. This can make the synchronization errors hard to detect, hard to reproduce and hard to verify that an error has been corrected.
Deadlocks can occur when multiple threads compete for the same set of multiple synchronization objects but acquire them in different orders. When one thread acquires a synchronization object, it exposes other threads that might also contend for that same synchronization object to a potential deadlock. As long as the first thread retains ownership of the synchronization object, the contending threads will typically be suspended whenever they attempt to acquire that synchronization object. The thread that holds the synchronization object may attempt to acquire another synchronization object. If this synchronization object is held by one of the contending, suspended threads, a deadlock can occur.
In order to illustrate how a deadlock can be latent, FIG. 1 shows a simple illustration of two threads that acquire, hold, and release two synchronization objects. At an instruction 101, thread 1 acquires a synchronization object called “mu1.” Subsequently, thread 1 acquires synchronization object “mu2” at an instruction 103. At instructions 105 and 107, thread 1 releases synchronization objects mu2 and mu1, respectively.
At some point in time later, thread 2 acquires synchronization object mu2 at an instruction 109. Thread 2 then acquires synchronization object mu1 at an instruction 111. At instructions 113 and 115, thread 2 releases synchronization objects mu1 and mu2, respectively.
It should be understood that FIG. 1 only includes instructions that acquire and release the two synchronization objects. Nevertheless, the Figure. Illustrates that both thread 1 and thread 2 were potentially contending for the synchronization objects mu1 and mu2, but the sequence of execution of the threads did not cause a deadlock condition.
FIG. 2 shows a simple illustration of how the two threads of FIG. 1 can become deadlocked. At an instruction 201, thread 1 acquires synchronization object mu1. Thread 2 then executes and acquires synchronization object mu2 at an instruction 203. At an instruction 205, thread 2 attempts to acquire synchronization object mu1. However, synchronization object mu1 is currently being held by thread 1. Therefore, thread 2 is not able to acquire synchronization object mu1 and is suspended awaiting the availability of the synchronization object at an instruction 207.
Thread 1 continues execution and attempts to acquire synchronization object mu2 at an instruction 209. Since synchronization object mu2 is held by thread 2, thread 1 is not able to acquire the synchronization object and is suspended awaiting the availability of synchronization mu2 at an instruction 211. At this point, deadlock has occurred since thread 2 is waiting for a synchronization object that thread 1 holds and thread 1 is waiting on a synchronization object that thread 2 holds.
As shown, in multi-threaded programs a deadlock can be latent and only surface if the right (or wrong) execution sequence occurs. It would be beneficial to have new techniques for detecting and causing latent deadlocks in a multi-threaded program. Additionally, it would be beneficial to have techniques that increase the opportunity for latent deadlocks to manifest themselves without introducing new deadlocks into the program.